package code.oldCode.feishuSpecializedTraining.binary_tree;

import java.util.*;

import utils.TreeNode;

/**
 * @author 26029
 * @date 2025/3/10
 * @description
 */
public class MyBinaryTree {
    // 144. 二叉树的前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        // 非递归
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                list.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return list;
    }

    public List<Integer> preorderTraversal_(TreeNode root) {
        // 递归
        List<Integer> list = new ArrayList<>();
        preorderTraversal_DIGUI(root, list);
        return list;
    }

    public void preorderTraversal_DIGUI(TreeNode root, List<Integer> list) {
        if (root == null)
            return;
        list.add(root.val);
        preorderTraversal_DIGUI(root.left, list);
        preorderTraversal_DIGUI(root.right, list);
    }

    // 94. 二叉树的中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        // 非递归
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            list.add(node.val);
            node = node.right;
        }
        return list;
    }

    // 145. 二叉树的后序遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        // 非递归：（迭代）※
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null, node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            if (node.right == null || node.right == prev) {
                // 如果右面访问完
                list.add(node.val);
                prev = node;
                node = null;
            } else {
                // 如果右面没访问完
                stack.push(node);
                node = node.right;
            }
        }
        return list;
    }

    public List<Integer> postorderTraversal_(TreeNode root) {
        // 非递归：（非迭代）把树的左右反向看待，再先序遍历，再反转结果。
        // 但是！这样做只是得到了遍历的数组，而不是一次迭代！
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                list.add(node.val);
                stack.push(node);
                node = node.right;
            }
            node = stack.pop();
            node = node.left;
        }
        int left = 0, right = list.size() - 1;
        while (left < right) {
            int temp = list.get(left);
            list.set(left, list.get(right));
            list.set(right, temp);
            left++;
            right--;
        }
        return list;
    }

    // 102. 二叉树的层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null)
            return new ArrayList<>();
        List<List<Integer>> lists = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
            lists.add(list);
        }
        return lists;
    }
}
